package LRU缓存; // 定义包名

// 导入并发相关的工具类
import java.util.concurrent.ConcurrentHashMap; // 线程安全的HashMap实现
import java.util.concurrent.ConcurrentLinkedQueue; // 线程安全的队列实现
import java.util.concurrent.CountDownLatch; // 用于线程同步的计数器
import java.util.concurrent.ExecutorService; // 线程池接口
import java.util.concurrent.Executors; // 线程池工厂类
import java.util.concurrent.atomic.AtomicInteger; // 原子整数类
import java.util.concurrent.locks.Lock; // 锁接口
import java.util.concurrent.locks.ReadWriteLock; // 读写锁接口
import java.util.concurrent.locks.ReentrantReadWriteLock; // 可重入读写锁实现

public class ConcurrentLRU<K, V> { // 定义线程安全的LRU缓存类，支持泛型
    private final int maxCap; // 缓存的最大容量
    
    private ConcurrentHashMap<K, V> map; // 存储键值对的线程安全Map
    private ConcurrentLinkedQueue<K> keys; // 存储键的线程安全队列，用于维护访问顺序

    private ReadWriteLock readWriteLock = new ReentrantReadWriteLock(); // 创建读写锁
    private Lock writeLock = readWriteLock.writeLock(); // 获取写锁
    private Lock readLock = readWriteLock.readLock(); // 获取读锁

    public ConcurrentLRU(int maxCap){ // 构造函数
        if(maxCap < 0){ // 检查容量是否合法
            throw new IllegalArgumentException("Illegal max capacity: " + maxCap);
        }
        this.maxCap = maxCap; // 设置最大容量
        map = new ConcurrentHashMap<>(maxCap); // 初始化Map
        keys = new ConcurrentLinkedQueue<>(); // 初始化队列
    }

    public V put(K key, V value){ // 添加或更新缓存项
        writeLock.lock(); // 获取写锁
        try {
            if(map.containsKey(key)){ // 如果键已存在
                moveToTail(key); // 将键移到队列尾部
                map.put(key, value); // 更新值
                return value;
            }
            if(map.size() == maxCap){ // 如果缓存已满
                System.out.println("maxCap of cache reached");
                removeOldest(); // 移除最旧的项
            }
            keys.add(key); // 将新键添加到队列
            map.put(key, value); // 将键值对添加到Map
            return value;
        } finally {
            writeLock.unlock(); // 释放写锁
        }
    }
    public V get(K key){ // 获取缓存项
        readLock.lock(); // 获取读锁
        try {
            if(map.containsKey(key)){ // 如果键存在
                moveToTail(key); // 将键移到队列尾部
                return map.get(key); // 返回值
            }
            return null;
        } finally {
            readLock.unlock(); // 释放读锁
        }
    }
    public V remove(K key){ // 移除缓存项
        writeLock.lock(); // 获取写锁
        try {
            if(map.containsKey(key)){ // 如果键存在
                keys.remove(key); // 从队列中移除键
                return map.remove(key); // 从Map中移除键值对
            }
            return null;
        } finally {
            writeLock.unlock(); // 释放写锁
        }
    }
    private void moveToTail(K key){ // 将键移到队列尾部
        keys.remove(key); // 从队列中移除键
        keys.add(key); // 将键添加到队列尾部
    }
    private void removeOldest(){ // 移除最旧的缓存项
        K oldest = keys.poll(); // 获取并移除队列头部的键
        if(oldest != null){ // 如果队列不为空
            map.remove(oldest); // 从Map中移除对应的键值对
        }
    }
    public int size(){ // 获取当前缓存大小
        return map.size();
    }
    public static void main(String[] args) throws InterruptedException{ // 主方法
        // 测试代码（已注释）
        // ---------------------------------------------------------------------
        int threadNum = 3; // 设置线程数
        int batch = 10; // 设置每批处理的数量
        ConcurrentLRU<String, Integer> lru = new ConcurrentLRU<>(batch * 3); // 创建LRU缓存实例
        ExecutorService threadPool = Executors.newFixedThreadPool(threadNum); // 创建线程池
        CountDownLatch latch = new CountDownLatch(threadNum); // 创建计数器
        AtomicInteger atomicInteger = new AtomicInteger(0); // 创建原子计数器
        long start = System.currentTimeMillis(); // 记录开始时间
        for(int t = 0; t < threadNum; t++){ // 创建多个线程
            threadPool.submit(() -> {
                for(int i = 0; i < batch; i++){ // 每个线程执行batch次操作
                    int val = atomicInteger.incrementAndGet(); // 原子递增
                    lru.put("id" + val, val); // 将值存入缓存
                }
                latch.countDown(); // 计数器减一
            });
        }
        latch.await(); // 等待所有线程完成
        threadPool.shutdown(); // 关闭线程池
        System.out.println("cache size:" + lru.size()); // 输出缓存大小
        long end = System.currentTimeMillis(); // 记录结束时间
        long duration = end - start; // 计算耗时
        System.out.println(String.format("cost time %dms", duration)); // 输出耗时
    }
}
